00100	CART PROJECT						    JUNE 1972
00200	
00300	
00400	                 OCCULT - A HIDDEN LINE ELIMINATOR.
00500	
00600	                              Baumgart

00700	
00800	
00900	
01000		OCCULT may be characterized as a hidden line eliminator  even
01100	though  it  does  not directly generate line drawings but is rather a
01200	marking and editing operation on a  3D  data  structure.  Consquently
01300	OCCULT  is  as much a hidden surface eliminator or a shadow caster as
01400	it is a line eliminator.
01500	
01600		The  general idea in OCCULT is that somehow a vertex is found
01700	to be hidden below a face or to be visible above a  face;  in  either
01800	event  the edges that form that vertex can be presumed to be likewise
01900	hidden or visible for some portion of their length starting from  the
02000	known  vertex. Following a hidden edge only requires checking whether
02100	that edge leaves its "over-face", whereas following  a  visible  edge
02200	requires  both  checking  whether the edge leaves its "under-face" as
02300	well as checking for a possible  "fold  crossing",  this  requires  a
02400	"fold  scan" which is where the algorithm spends most of its time. At
02500	crossings the 3D data structure is altered and two new  vertices  are
02600	created to form a "T-joint".
02700	
02800		The  reason for doing hidden line elimination in this fashion
02900	is to obtain the edge and region topology of an image for the sake of
03000	a  computer  vision  by  verification  scheme. OCCULT's alleged "high
03100	speed" was not a design goal and is not really a consequence  of  the
03200	HIDE  or  SHOW  edge  following  but rather comes from doing the hard
03300	things prior to hidden line elimination, such as finding  conflicting
03400	bodies,  and  from the speed of the Winged Edge BFEV primitives which
03500	efficiently access and modify oriented edge structures.
     

00100		Prior  to  any  hidden  line eliminator, HLE, there must be a
00200	model maker. Indeed one of the nasty pitfalls in computer graphics is
00300	to  invest your time, money and energy in studying or building hidden
00400	line eliminators and neglecting your model data structures  and  your
00500	model builders. Pretty pictures result from big complicated models, a
00600	HLE is only a translator or compiler, and little or nothing  in  will
00700	result  in  little or nothing out. The model builder that I used with
00800	OCCULT is called GEOMED [ref. x] and its data structures and  two  of
00900	its primitives will be briefly explained here.
01000	
     

00100	THE MAIN CONTEXT OF OCCULT.
00200	
00300		The  main  Context  of  OCCULT is held in four sets. There is
00400	POTNTF, which is the set of potential visible faces. There is POTNTE,
00500	which is the set of potential visible edges. There is FOLDE, which is
00600	the set of potential visible folded edges. There is VISINC, which  is
00700	the  set  of  visible folded edges which are incomplete, that is only
00800	one of there ends is visible.
     

00100	GLOSSARY
00200	
00300	HLE......hidden line eliminator.
00400	POTENT.....potential visible.
00500	BFEV.......Body, Face, Edge, Vertex.
00600	UNDERFACE.........
00700	OVERFACE.........
00800	JOT.............Joint Over T.
00900	JUT.............Joint Under T.
     

00100		Body, Face, Edge, Vertex - Winged Data Structure.
00200	
00300		GEOMED primitives - ESPLIT.
00400	
00500	Terminology.
00600	
00700		The visibility of each face, edge and vertex is
00800	characterized by two bits, POTENT and VISIBLE.
00900	The POTENT bit indicates that the entity is still potentially
01000	visible,
01100	
01200		0 0  indicates hidden.
01300		1 0  indicates potentially visible.
01400		0 1  indicates  actually   visible.
01500		1 1  undefined.
01600	
01700	INPUT MODEL RESTRICTIONS.
01800	
01900		OCCULT is a "weak" hidden line eliminator in the sense
02000	it requires convex, coplanar, non-intersecting faces. However,
02100	
02200		Concave Face Elimination.
02300		Conflicting Body Elimination.
02400	
02500	Initialization.
02600		Z-clipping.
02700		Perspective Project Vertices
02800		Face Coefficients and POTENT faces.
02900		POTENT edges and Edge Coefficients.
03000		FOLDED edges.
03100	
03200	A folded edge is an edge that has a single POTENT face.
03300	An edge with two POTENT faces is termed a "seam" or "crease".
     

00100	The main part of OCCULT consists of six subroutines:
00200	
00300		VHIDE		VSHOW
00400		EHIDE		ESHOW
00500		MKTJ1		MKTJ2
00600	
00700	The simplist of which is VHIDE(F,V) which when given that
00800	a vertex V has somehow been found to lie within and under
00900	a face F, marks that vertex as hidden and then attempts
01000	to hide all the POTENT edges of that vertex by calling EHIDE.
01100	
01200	EHIDE(F,E,V)	Attempts to hide as much of an edge E as
01300	is possible starting from V which is known to be hidden.
01400	There are essentially three basic cases: the edges
01500	never leaves the face covering V, the edge leaves but
01600	crosses under a seam into another occultating face
01700	or the edge crosses under a fold and EHIDE must make
01800	a T-joint by calling MKTJ1 in order to leave a portion of
01900	the edge potentially visible. EHIDE gets slightly more
02000	complicated in that the edge being hidden can rise up
02100	and strike from below one of the vertices of its covering
02200	face.
02300	
02400	MKTJ1(FOLD,EDGE,V1) splits the Fold and the Edge and
02500	forms a T-Joint.